1534G - A New Beginning - CodeForces Solution

/*
君は瞬きと共に過ぎてく時間も
遠くから見てると微笑んで
 */
/*author::ღꦿ࿐(DeepSea.) */
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
const int N = 1e6 + 20 ;
#define nxtl puts("")
using ll = long long ; 
using ull = unsigned ll;
using vi = vector<int> ;
using vl = vector<ll> ;
using pi = pair<int,int> ;
using pl = pair<ll,ll> ;
#define All(x) x.begin(),x.end()
#define Hash __gnu_pbds::gp_hash_table
#define Heap __gnu_pbds::priority_queue
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define Rep(i,y,x) for(int i=y;i>=x;--i)

namespace IO {
    char *p1=NULL,*p2=NULL,buf[1<<20];
    inline void read(char *x) ; 
    template<typename _Tp>inline void wrt(_Tp x) ;
    template<typename _Tp> inline void wrt(vector<_Tp> &vec,char c) ; 
    template<typename _Tp> inline void read(vector<_Tp> &vec,int n) ; 
    inline void wrt(char ch); inline void wrt(char *s);  inline void wrt(const char *s);
    template<typename _Tp>inline void read(_Tp &x); template<typename _Tp>inline void nread(_Tp &x) ;
    template<typename _Tp,typename ...Args> inline void wrt(_Tp x,Args ...args){wrt(x),wrt(args...);}
    template<typename _Tp,typename ...Args> inline void read(_Tp &x,Args &...args){read(x),read(args...);}
}
namespace _{
    int _;
    #ifdef DEBUG 
    template<typename _Tp>void s(char c,_Tp x) ; template<typename _Tp>void s(char a,char b,_Tp x,_Tp y) ; 
    template<typename _Tp>void s(char c,vector<_Tp> vec) ;   
    #else
    #define s(...) _ 
    #endif 
}
using IO::read; using IO::wrt; 

int n ;
pi pt[N] ;
struct heap1 {
    priority_queue < int , vector<int> , greater<int> > h; 
    int del ;
    void emplace(int x) {
        h.emplace(x - del) ;
    }
    void shift(int x) {
        del += x ;
    }
    int top( ) {return h.top( ) + del; }
    void pop( ) { h.pop( ) ;}
    unsigned int size( ) {return h.size( ) ;}
} r ;
priority_queue < int> l ;
ll ans ;
bool cmp(pi x,pi y) {
    return x.first + x.second < y.first + y.second ;
}

signed main()
{
    read(n) ;
    rep(i,1,n) read(pt[i].first , pt[i].second),ans += pt[i].second;
    l.emplace(0) , r.emplace(0) ;
    sort(pt + 1 , pt + n + 1 ,cmp) ;
    rep(i,1,n) {
        r.shift(pt[i].first + pt[i].second - pt[i - 1].first - pt[i - 1].second) ;
        int v = pt[i].second ;
        if(v < l.top( )) {
            l.emplace(v) , l.emplace(v) ;
            r.emplace(l.top( )) ; l.pop( );
        }
        else if(v > r.top( )) {
            r.emplace(v) , r.emplace(v) ;
            l.emplace(r.top( )) ; r.pop( );
        } else {
            l.emplace(v) , r.emplace(v) ;
        }
        
    }
    rep(i,1,n + 1) ans -= l.top( ) , l.pop( ) ;
    cout << ans << '\n' ;
    return 0;
}


























































using IO::p1 ;
using IO::p2 ;
using IO::buf; 
#ifdef DEBUG
#define gchar() getchar()
template<typename _Tp>void _::s(char c,_Tp x) {cout << c << " = " << x << '\n' ;}
template<typename _Tp>void _::s(char a,char b,_Tp x,_Tp y) {cout << "(" << a << "," << b << ") = (" << x  << "," << y << ")\n";}
template<typename _Tp>void _::s(char c,vector<_Tp> vec) {
    cout << c << " siz = " << vec.size( ) << '\n' ;
    for(auto &x:vec) cout << x << ' ' ;
}  
#else
#define gchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
inline void IO::wrt(char ch){putchar(ch);}
inline void IO::wrt(char *s){while(*s!='\0')putchar(*s++);}
inline void IO::wrt(const char *s){while(*s!='\0')putchar(*s++);}
inline void IO::read(char *x){
    char ch=gchar();
    while(ch==' '||ch=='\n'||ch=='\r')ch=gchar();
    do *x++=ch,ch=gchar(); while(ch!=' '&&ch!='\n'&&ch!='\r');
    *x='\0';
}
template<typename _Tp>inline void IO::read(_Tp &x){
    x=0;_Tp f=1;char ch=gchar();
    for(;!isdigit(ch);ch=gchar())ch=='-'&&(f=-1);
    for(;isdigit(ch);ch=gchar())x=(x<<1)+(x<<3)+(ch^48);
    x*=f;
}
template<typename _Tp>inline void IO::wrt(_Tp x){
    if(x<0)x=-x,putchar('-');
    if(x>9)wrt(x/10);
    putchar(x%10+48);
}
template<typename _Tp> inline void IO::wrt(vector<_Tp> &vec,char c){
    for(_Tp &e:vec) wrt(e,c); 
}
template<typename _Tp> inline void IO::read(vector<_Tp> &vec,int n) {
    vec.resize(n) ; for(_Tp &e:vec) read(e) ;
}